home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
FishMarket 1.0
/
FishMarket v1.0.iso
/
fishies
/
351-375
/
disk_366
/
makewords
/
source
/
phoneword.c
< prev
next >
Wrap
C/C++ Source or Header
|
1992-05-06
|
9KB
|
340 lines
/* PhoneWord.c - try to make words from a phone number.
Ron Charlton
9002 Balcor Circle
Knoxville, TN 37923
Phone: (615)694-0800
PLINK: R*CHARLTON
BINTNET: charltr@utkvx1
05-Jul-90
This program is in the public domain. It may be used for any purpose.
Algorithm: Generate all of the permutations of the letters in a phone number
and test each one for its "trigram weight". (A trigram is a group of three
letters, e.g., AAA, EWE, QQQ.) Use a table of trigram weights (frequencies)
derived from a 38,500 word dictionary. Calculate an n-letter string's
trigram weight as the sum of the weights of its (n - 2) trigrams. A
trigram's weight is its frequency of occurrence in the dictionary.
Keep a table of the twenty highest weights while avoiding duplicates due to
multiple occurrences of a single letter. Print out only the non-zero
entries in the table. This all works because some trigrams (such as "ING")
are more likely than others (such as "QQQ").
history:
v1.2 converted to be the 'same' as Unjumble.c v1.14
*/
char version[] = "v1.2";
#include <stdio.h>
#include <ctype.h>
#define FALSE 0
#define TRUE (!FALSE)
#ifdef MCH_AMIGA
#define CSI 0x9b
#define CLS 0x0c
#endif
#define MAPVALUE ('a'-1) /* 'A' for uppercase, 'a' for lowercase */
#define MAXDIGITS 7
#define MAXLEN MAXDIGITS /* max. length of string */
#define TABLESIZE 20 /* size of table of guesses */
/* read a nybble from a table of nybbles (32-bit longs in table) */
#define READ_NYBBLE( nyb_number ) \
( (nybble_table [ nyb_number >> 3 ] >> ((nyb_number & 7L) << 2)) & 0xFL )
/* test bit n in table of 32-bit ints */
#define TEST_BIT( n ) \
( bit_table [ n >> 5 ] & ( 1L << (n & 0x1FL) ) ? 1 : 0 )
/* the follow two lines are associated with tables.c */
extern int bit_table_size, nybble_table_size;
extern unsigned long bit_table[], nybble_table[];
/* structure array to hold candidate words and their weights */
struct {
char word [ MAXLEN + 1 ];
int weight;
} table [ TABLESIZE ];
unsigned char nn[27][27][27]; /* array of probabilities of trigrams */
int i [ MAXDIGITS ];
/* here are the letters on the phone dial (none for 0 & 1) */
char letters [][4] = { "@@@", "@@@", "ABC", "DEF", "GHI", "JKL", "MNO",
"PRS", "TUV", "WXY" };
char Dstr [ 255+1 ]; /* string from user */
char work [ MAXDIGITS+1 ]; /* build string to test here */
int min_weight; /* used in insert() for minimum weight */
int min_weight_ptr; /* used in insert() to point at minimum */
/*------------------------------------------------------------------------*/
main()
{
int dig_pos, length, good;
intro();
get_weights();
do
{
good = TRUE;
init_table();
printf ( "\tEnter 2 to 7 digits (no 1 or 0) <RETURN> to quit): " );
gets ( Dstr );
length = strlen ( Dstr );
if ( length == 0 ) exit ();
if ( length > MAXDIGITS )
{
printf ( "\t\tEnter no more than %d digits.\n\n", MAXDIGITS );
continue;
}
/* check for bad characters ( only 2-9 allowed ) */
for ( dig_pos = 0; dig_pos < length; dig_pos++ )
{
if ( !isdigit ( Dstr [ dig_pos ] ) || Dstr [ dig_pos ] == '1' ||
Dstr [ dig_pos ] == '0' )
{
printf ( "\t\tOnly digits 2-9 allowed.\n\n" );
good = FALSE;
break;
}
Dstr [ dig_pos ] -= '0';
}
if ( good )
switch ( length )
{
case 1:
printf ( "\t\tThat's too easy.\n\n" );
break;
case 2:
do_two();
break;
case 3:
case 4:
case 5:
case 6:
case 7:
generate ( 0, length ); /* generate all of the possibilies */
print_table(); /* display the results */
break;
default:
break;
}
} while ( length > 0 );
}
/*------------------------------------------------------------------------*/
intro()
{
#ifdef MCH_AMIGA
printf ( "%c", CLS ); /* clear screen */
printf ( "%c0;33;40m", CSI ); /* color 3,0 */
#endif
printf ( "\n\t\t\t PhoneWord %s\n\n", version );
printf ( "\t\t\t by\n" );
printf ( "\t\t\t Ron Charlton\n" );
printf ( "\t\t\t 9002 Balcor Circle\n" );
printf ( "\t\t\t Knoxville, TN 37923\n" );
printf ( "\t\t\t Plink: R*CHARLTON\n" );
printf ( "\t\t\t BITNET: charltr@utkvx1\n\n" );
#ifdef MCH_AMIGA
printf ( "%c0;31;40m", CSI ); /* color 1,0 */
#endif
printf ( "\tPhoneWord tries to create words out of telephone numbers\n" );
printf ( "\tthat you enter. It will print out up to twenty guesses in\n" );
printf ( "\torder with each guess' weight before it. One and zero\n" );
printf ( "\tare not accepted. Seven digits requires several seconds'\n");
printf ( "\tcalculation. If there is no guess, then it is noted.\n\n" );
printf ( "\tIf your number has 1 or 0 in it you can enter the other\n" );
printf ( "\tdigits in several groups. It is good to try different\n" );
printf ( "\tgroups of digits anyway, for example, if your number is\n" );
printf ( "\t234-5678, then try 234 & 5678; 2345 & 678; 23456 & 78;\n" );
printf ( "\t2345678, etc.\n\n" );
}
/*------------------------------------------------------------------------*/
do_two()
/* do simple case of two digits */
{
int ii, jj;
for ( ii = 0; ii < 3; ii++ )
for ( jj = 0; jj < 3; jj++ )
printf ( "\t\t%c%c\n", letters [ Dstr[0] ] [ii], letters [ Dstr[1] ] [jj]);
}
/*------------------------------------------------------------------------*/
generate ( pos, len )
/* generate the "words" recursively (creates "len" nested "for" loops) */
int pos, len;
{
int s;
if ( pos < len )
for ( i [ pos ] = 0; i [ pos ] < 3; ++i[pos] )
{
generate ( pos+1, len );
}
else
{
/* build string and test it */
for ( s = 0; s < len; s++ )
work [ s ] = letters [ Dstr[s] ] [ i[s] ] - '@';
work [ s ] = '\0';
insert ( work ); /* insert into table if weighty */
}
}
/*------------------------------------------------------------------------*/
/* find sum of weights of trigrams in a string. */
weigh ( str )
char *str;
{
register int weight = 0, len, pos, triweight;
if ( (len = strlen ( str ) ) >= 3 )
for ( pos = 0; pos <= len - 3; pos++)
{
triweight = nn [ str [pos] ] [ str [pos+1] ] [ str [pos+2] ];
if ( triweight > 0 )
weight += triweight;
else
{
/* eliminate those with any trigram of 0 weight */
weight = 0;
break;
}
}
return ( weight );
}
/*------------------------------------------------------------------------*/
/* convert array indices to alphabetic 1-->A, 2-->B ... 26-->Z */
unmap ( str )
char *str;
{
while ( * str )
*str++ += MAPVALUE;
}
/*------------------------------------------------------------------------*/
/* initialize the guess table to empty */
init_table()
{
int i;
min_weight = 0;
min_weight_ptr = 0;
for ( i = 0; i < TABLESIZE; i++)
{
table[i].weight = 0;
table[i].word[0] = '\0';
}
}
/*------------------------------------------------------------------------*/
/* if this is a weighty word, insert it in the table */
insert ( str )
char *str;
{
register int weight, i;
weight = weigh ( str );
if ( weight > min_weight ) /* does this word weigh more than table min.? */
{
for ( i = 0; i < TABLESIZE; i++ ) /* avoid duplicates (BIGgER BIgGER) */
if ( ! strcmp ( table[i].word, str ) )
return; /* it's already in the table */
/* put this one in table in place of old minimum */
table [ min_weight_ptr ].weight = weight;
strcpy ( table [ min_weight_ptr ].word, str );
/* search for new minimum in the table */
min_weight_ptr = 0;
min_weight = table [ 0 ].weight;
for ( i = 1; i < TABLESIZE; i++ )
if ( table [ i ].weight < min_weight )
{
min_weight_ptr = i;
min_weight = table [ i ].weight;
}
}
}
/*------------------------------------------------------------------------*/
/* print the non-zero table entries in descending order. */
/* this is a bogus, but adequate, sort */
print_table()
{
int max_entry, i, first_pass = TRUE;
for(;;)
{
max_entry = 0; /* point at maximum weight */
for ( i = 1; i < TABLESIZE; i++ )
if ( table [ i ].weight > table [ max_entry ].weight )
max_entry = i;
if ( first_pass && table [ max_entry ].weight == 0 )
{
printf ( "\t\tNothing found.\n" );
break;
}
if ( table [ max_entry ].weight )
{
unmap ( table [ max_entry ].word );
printf("\t\t%5d %s\n", table [ max_entry ].weight,
table [ max_entry ].word );
table [ max_entry ].weight = 0; /* 'delete' from table */
}
else
break;
first_pass = FALSE;
}
}
/*------------------------------------------------------------------------*/
/* get trigram weights from nybble_table and bit_table into nn[][][] */
get_weights()
{
register int i, j, k, m = 0, ptr = 0;
for ( i = 1; i <= 26; i++ )
for ( j = 1; j <= 26; j++ )
for ( k = 1; k <= 26; k++ )
{
/* beware of ++x side effects */
if ( TEST_BIT ( m ) )
{
nn [ i ] [ j ] [ k ] = READ_NYBBLE ( ptr );
++ptr;
}
++m;
}
}
/*-------------------------- END OF FILE---------------------------------*/